The most widespread streaming encryption method generates an encryption series independently of the message to be encrypted using linear feedback shift registers to save on hardware.
The major drawback of linear feedback shift registers is their linearity. Knowing a number of output bits of the register equal to the length of the register and the feedback polynomial associated with the register makes it possible to determine the output bits and all subsequent states of the register.
To “break” the linearity of linear feedback shift registers, the outputs of a plurality of registers, and possibly their internal states, are commonly combined, for example using a non-linear Boolean function.
FIG. 6 shows a generator 100 of this kind, known as a shrinking generator, described in European Patent Application EP 0 619 659 and including a first linear feedback shift register 111a, a second linear feedback shift register 111b, and means 112 for selecting the output of the generator 100.
Thus, on each shift, the two registers 111a and 111b are shifted simultaneously, and the output of the device 100 is equal to the output of the second register 111b if the output of the first register 111a is “1”; if not, no bit is output.
The shrinking generator combines not only the outputs of two linear feedback shift registers but also, more generally, any pair of series of bits. The shrinking generator is part of a class of streaming encryption methods in which one linear feedback shift register controls another. The idea is to vary the number of shifts between the registers employed and between two consecutive bits, in order to break the linearity of the registers.
A variant of the shrinking generator, called the self-shrinking generator, is based on the same principle but uses only one register. The output bits of the register are read two by two, and the first bit controls whether the second bit is output, so that the output of the system is the second bit if the first bit is a “1”; if not, no bit is output.
Using only linear feedback shift registers has numerous drawbacks. The main one is the vulnerability caused by the linearity of the device. There are also drawbacks if registers are combined by a Boolean function. At hardware level, they are a result of the complexity of the function implementation. Moreover, the function is fixed and can be attacked.
Statistical methods have shown up certain weaknesses of the shrinking generator and other clock-controlled encryption methods. In particular, in the shrinking generator, the number of shifts effected by the two registers between two output bits varies, but has the same value for both registers.